package c_heap.b_max_index_heap;

/**
 * 索引堆的优化
 *
 * 之前change操作对索引交换的时候从一边进行，时间复杂度编程 O(N) 效率低下
 * 解决办法：
 * 增加一个rvs数据 维护 data索引i（从1开始）在idx数组中的位置
 * 这样就可以使用O(1)的复杂度找到欲修改数据对应的索引在idx数组中的位置
 * 然后直接对这个位置进行shiftDown和shiftUp操作即可
 *
 * rvs代表反向的意思 即 将idx的索引和对应的值反向，如下：
 * idx[i] = j;
 * rvs[j] = i;
 * 同理可以推导出：
 * idx[rvs[i]] = i;
 * rvs[idx[i]] = i;
 *
 * 这是一种典型的空间交换时间的算法思想
 *
 */
@SuppressWarnings("unchecked")
public class MaxIndexBinaryHeapAdvance<Item extends Comparable<Item>> {
    private Item[] data; // 数据数组
    private int[] idx; // 数据在堆中的索引
    private int[] rvs; // idx的反转数组 - 索引和值的翻转

    private int count; // 堆中元素数量
    private int capacity; // 堆中可容纳元素数量

    public MaxIndexBinaryHeapAdvance(int capacity) {
        this.capacity = capacity;
        count = 0;
        data = (Item[]) new Comparable[capacity + 1];
        idx = new int[capacity + 1];
        rvs = new int[capacity + 1];
    }

    public MaxIndexBinaryHeapAdvance(Item[] arr) {
        capacity = arr.length;
        data = (Item[]) new Comparable[capacity + 1];
        idx = new int[capacity + 1];
        rvs = new int[capacity + 1];


        for (int i = 0; i < capacity; i++) {
            data[i + 1] = arr[i]; // 初始化数据
            idx[i + 1] = i + 1; // 初始化数据索引
            rvs[idx[i+1]]=i+1;
        }
        count = capacity;
        for (int i = count / 2; i >= 1; i--) {
            shiftDown(i); // 对索引进行交换
        }
    }

    public int size() {
        return count;
    }

    public boolean isEmpty() {
        return count == 0;
    }

    /**
     * 判断data中索引k的位置是否存在数据
     * @param i
     * @return
     */
    boolean contain(int i) {
        i++;
        assert (i >= 1 && i <= capacity);
        return rvs[i] != 0;
    }
    /**
     * 插入一个新元素
     * 返回新的最大堆的元素数
     *
     * @param item
     * @return
     */
    public int unshift(Item item) {
        assert count <= capacity - 1;
        count++;
        data[count] = item;
        idx[count] = count;
        rvs[count] = count;
        shiftUp(count); // 向上交换 - 维护最大堆的性质
        return count;
    }

    /**
     * 在索引i插入数据
     *
     * @param i    对调用者而言， 从0开始
     * @param item
     */
    public void insert(int i, Item item) {
        assert count + 1 <= capacity;
        assert (i + 1 >= 1 && i + 1 <= capacity);
        i++;
        data[i] = item;
        idx[count + 1] = i;
        rvs[i] = count + 1;
        count++;
        shiftUp(count);
    }

    /**
     * 最大堆中插入元素后
     * 需要逐级和父元素比较
     * 如果比父元素还大就向上进行shiftUp(向上交换数据索引)操作
     *
     * @param k 新插入元素在data中的索引
     *          新插入元素如果比父节点大就和父节点交换位置 - 维护最大堆的性质
     *          即堆中某个节点的值总是不大于其父节点的值
     */
    private void shiftUp(int k) {
        // k=1时 只有一个根元素 不存在和父元素交换数据索引
        // 只有当k>1时且k的元素比父元素k/2还大的时候才需要交换数据索引
        while (k > 1 && data[idx[k / 2]].compareTo(data[idx[k]]) < 0) {
            swapIdx(k, k / 2);
            k /= 2; // 继续向父元素进行迭代
        }
    }

    /**
     * 删除并同时返回堆顶的最大元素
     *
     * @return 堆顶元素
     * 1. 将堆顶元素和队尾元素交换
     * 2. 从堆顶元素开始进行向下交换 - 维持最大堆性质
     */
    public Item shiftItem() {
        Item ret = data[idx[1]];
        swapIdx(1, count);
        count--;
        shiftDown(1);
        return ret;
    }

    /**
     * 删除堆顶元素
     * 返回索引数组中堆顶元素的索引的索引位置
     *
     * @return
     */
    public int shiftIndex() {
        assert (count > 0);
        int ret = idx[1] - 1;
        swapIdx(1, count);
        count--;
        shiftDown(1);
        return ret;
    }

    /**
     * 返回堆顶最大元素
     *
     * @return
     */
    public Item getMax() {
        assert count > 0;
        return data[idx[1]];
    }

    /**
     * @param k 向下交换的起始下标
     */
    private void shiftDown(int k) {
        while (2 * k <= count) { // 如果k有孩子 - 完全二叉树来说有左孩子就必有右孩子， 所以只需考察是否有左孩子
            int j = 2 * k; // 预设和左孩子交换
            if (j + 1 <= count && data[idx[j + 1]].compareTo(data[idx[j]]) > 0) {
                j++; // 当右孩子比左孩子大的时候 预设交换元素就改成右孩子
            }
            // 如果操作的元素已经大于或等于它最大的孩子，交换过程结束
            if (data[idx[k]].compareTo(data[idx[j]]) >= 0) break;
            // 反之 和 其最大孩子进行交换
            swapIdx(k, j);
            // 并继续考察交换后的元素的父元素 -
            k = j;

        }
    }

    /**
     * 翻转idx的啷个位置
     * 同时翻转rvs
     * @param m
     * @param n
     */
    private void swapIdx(int m, int n) {
        int temp = idx[m];
        idx[m] = idx[n];
        idx[n] = temp;
        rvs[idx[m]]=m;
        rvs[idx[n]]=n;
    }


    /**
     * 根据索引（从0开始）获取data中的数据
     * @param k
     * @return
     */
    public Item get(int k) {
        assert contain(k);
        return data[k +1]; // data数据时从1开始存放的
    }

    /**
     * 修改根据索引修改data的数据
     *
     * @param k 需要修改的数据在data的索引 - 从0开始计数
     * @param item 1. 替换data数据
     *             2. 对被修改数据的索引向上和向下交换 - 使得整个数据保持最大堆的性质
     */
    public void put(int k, Item item) {
        assert contain(k);
        // 修改数据
        data[++k] = item; // data从1开始计数
        // 修改数据索引
        //for (int j = 1; j <= count; j++) {
        //    if (idx[j] == k) { // 找到k在数据索引中的位置
        //        shiftUp(j);
        //        shiftDown(j);
        //        return;
        //    }
        //}
        int j = rvs[k];// 反向查找k在idx中的位置
        shiftUp(j);
        shiftDown(j);
    }

    /**
     * 打印测试
     */
    public void printHeapDataTest() {
        if (count == 0) {
            System.out.println("该堆中不包含任何数组");
            return;
        }
        if (size() >= 100) {
            System.out.println("该测试方法只能打印不超过100个容量的堆的树形结构");
            return;
        }
        if (!(data[1] instanceof Integer)) {
            System.out.println("该测试方法只能处理整数数据");
            return;
        }

        System.out.print("RVSE[" + size() + "] : ");
        for (int i = 1; i <= size(); i++) {
            System.out.print((rvs[i]-1) + " ");
        }
        System.out.print("\n");
        System.out.print("INDX[" + size() + "] : ");
        for (int i = 1; i <= size(); i++) {
            System.out.print((idx[i] - 1) + " ");
        }
        System.out.print("\n");
        System.out.print("DATA[" + size() + "] : ");
        for (int i = 1; i <= size(); i++) {
            System.out.print(data[i] + " ");
        }
        System.out.print(" |MAX| " + " -> " + getMax());
        System.out.print("\n===================================================\n");
    }

    /**
     * 打印测试
     * 依次出队， 从大到小打印
     */
    public void printHeapDescSortedTest() {
        int len = size();
        System.out.print("HEAP[" + len + "] : ");
        for (int i = 0; i < len; i++) {
            Item item = shiftItem();
            System.out.print(item + " ");
        }
        System.out.print(" <-- sorted desc \n");
    }

    /**
     * 打印测试
     * 传入原数组， 返回从小到大排序好的数组
     * 同时打印测试输出
     */
    public void printHeapAscSortedTest() {
        int len = size();
        Comparable[] ret = new Comparable[len];
        for (int i = len - 1; i >= 0; i--) {
            ret[i] = shiftItem();
        }
        System.out.print("HEAP[" + len + "] : ");
        for (int i = 0; i < len; i++) {
            System.out.print(ret[i] + " ");
        }
        System.out.print(" <-- sorted asc \n");
    }

    public static void main(String[] args) {
        MaxIndexBinaryHeapAdvance<Integer> maxHeap = new MaxIndexBinaryHeapAdvance<>(100);
        for (int i = 0; i < 15; i++) {
            int num = (int) (Math.random() * 100);
            maxHeap.insert(maxHeap.size(),num);
//            maxHeap.unshift(num);
        }
        maxHeap.printHeapDescSortedTest(); // 打印完后数组清空


        Comparable[] arr = {3, 2, 5, 4, 1, 0, 21, 52, 12, 64, 2};
        MaxIndexBinaryHeapAdvance maxheap2 = new MaxIndexBinaryHeapAdvance(arr);
        maxheap2.printHeapAscSortedTest();


        MaxIndexBinaryHeapAdvance maxheap3 = new MaxIndexBinaryHeapAdvance(arr);
        maxheap3.printHeapDataTest();
        maxheap3.put(0,99);
        maxheap3.printHeapDataTest();
        for (int i = 0; i < maxheap3.size(); i++) {
            System.out.print(maxheap3.get(i) + " ");
        }
        System.out.println();
    }
}